package org.lanqiao.practice_2;

public class TestDriver5 {
	// //测试二分法排序 垃圾程序
	public static void main(String[] args) {
		int[] ar = { 4, 2, 1, 6, 3, 6, 0, -5, 1, 1 };
		int[] a = halfSort(ar);
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + "  ");
		}
	}
	// int i,j;
	// int low,high,mid;
	// int temp;
	// for(i=1;i<10;i++){
	// temp=ar[i];
	// low=0;
	// high=9+1;
	// while(low<=high){
	// mid=(low+high)/2;
	// if(ar[mid]>temp){
	// high=mid-1;
	// }else{
	// low=mid-1;
	// }
	// }
	// for(j=i-1;j>high;j--){
	// ar[j+1]=ar[j];
	// ar[high+1]=temp;
	// }
	//
	// for(i=0;i<10;i++){
	// System.out.println(ar[i]+" ");
	// }
	// }
	// }

	// /**
	// * @param ar 需要排序的数组
	// */
	// public static void halfSort(int []ar){
	// for(int i=0;i<)
	// }
	//

	/**
	 * @param data 百度上的二分法
	 * @return
	 */
	public static int[] BarnarySort(int[] data) {
		int[] temp = new int[data.length];
		for (int i = 0; i < temp.length; i++) {
			if (i == 0) {
				temp[i] = data[i];
			} else {
				for (int j = 0, k = i - 1; j < i && k >= 0;) {
					if (temp[(j + k) / 2] >= data[i]) {
						if ((j + k) / 2 == 0) {
							for (int iter = i; iter > 0; iter--) {
								temp[iter] = temp[iter - 1];
							}
							temp[0] = data[i];
							break;
						} else if (temp[(j + k) / 2 - 1] <= data[i]) {
							for (int iter = i; iter > (j + k) / 2; iter--) {
								temp[iter] = temp[iter - 1];
							}
							temp[(j + k) / 2] = data[i];
							break;
						} else {
							k = (k + j) / 2 - 1;
						}
					} else if (temp[(j + k) / 2] < data[i]) {
						if ((j + k) / 2 == i - 1) {
							temp[i] = data[i];
							break;
						} else {
							j = (k + j) / 2 + 1;
						}
					}
				}
			}
		}
		return temp;
	}

	/**
	 * 二分法查找
	 */
	public static int[] halfSort(int[] ar) {
		// 定义一个和传进来的数组长度一样的数组
		int[] a = new int[ar.length];
		// 先把第一个数赋值给新创建的数组
		a[0] = ar[0];
		for (int i = 1; i < ar.length; i++) {
			// 进行二分查找
			for (int j = 0, k = i - 1; j < i && k >= 0;) {
				// 判断二分之后的数在哪个位置
				if (a[(j + k) / 2] >= ar[i]) {
					// 处理当前这个段这个数最小时的情况
					if ((j + k) / 2 == 0) {
						for (int m = i; m > 0; m--) {
							a[m] = a[m - 1];
						}
						a[0] = ar[i];
						break;
					} else if (a[(j + k) / 2 - 1] <= ar[i]) {
						// 处理当前这个数在二分查找到在当前的情况
						for (int m = i; m > (j + k) / 2 - 1; m--) {
							//依次往后移位
							a[m] = a[m - 1];
						}
						a[(j + k) / 2 - 1] = ar[i];
						break;
					} else {
						k = (j + k) / 2 - 1;
					}
				} else {
					//处理当前这个数最大时的情况的
					if ((j + k) / 2 == i - 1) {
						a[i] = ar[i];
						break;
					} else {
						j = (j + k) / 2 + 1;
					}
				}
			}

		}
		return a;
	}

}
